In most conventional packet based network routing protocols, a router receives a packet and analyzes the packet header to determine the next hop for the packet between the source and intended destination. These decisions are typically made locally and independently of other routers, based solely on the analysis of the packet header, which contains the destination address. For example, routers using conventional Internet Protocol (IP) forwarding techniques typically look for a “longest prefix” match to the entries in the routing table to determine the next hop. In general, each router must extract the relevant information from the (much longer) packet header. Furthermore, routers are not designed to use information about the source of the packets from these headers for forwarding purposes.
An alternative routing protocol, proposed by the Internet Engineering Task Force (IETF), is referred to as MultiProtocol Label Switching (MPLS). The MPLS routing protocol is described, for example, in Bruce Davie and Yakov Rekhter, MPLS: Technology and Applications, Morgan Kaufmann Publishers (2000); or MPLS Charter, each incorporated by reference herein. The MPLS routing protocol analyzes a packet header just once, and causes the packet to be assigned a stack of labels, where the labels are usually much smaller than the packet headers themselves, as described in Eric C. Rosen et al., “MPLS Label Stack Encoding,” RFC 3032, incorporated by reference herein.
At each subsequent hop, the router examines the label at the top of the label stack, and makes the decision for the next hop based solely on that label. The router can then remove this label from the stack, if desired, and push zero or more labels onto the stack, before sending the packet to the next hop. The label replacement and the path followed by the packet are referred to as a Label Switched Path (LSP). It is noted that there is no further analysis of the network layer header by any of the subsequent routers.
There are a number of advantages of the MPLS routing protocol over conventional network layer forwarding, including the above-mentioned elimination of header analysis at each hop. A more significant benefit, however, is that since the header is analyzed and the stack is assigned to the packet when the packet enters the network, the ingress router may use any additional information about the packet to route packets differently to satisfy different quality of service (QoS) requirements. For example, data for time-sensitive applications may be sent along faster but more expensive Label Switched Paths than regular data. Also, the ingress router can encode information about the source as well as the destination in the labels, which cannot be done with conventional forwarding. In addition, traffic engineering is easier relative to conventional routing schemes, since the entire route taken by the packet can be specified very naturally on the stack. Thus, MPLS has become a popular packet routing protocol.
Nonetheless, little is known about the performance that can be achieved with MPLS, and about the intrinsic trade-offs in the use of resources under the MPLS protocol. It has been observed that a good routing protocol is one that uses a minimum possible set of labels (to enhance router performance), while pushing the minimum possible number of labels on the stack for each packet (to keep the packet sizes small). Unfortunately, there is a trade-off involved here, and the two goals of minimizing label sizes and minimizing stack depths are conflicting. A need therefore exists for a method and apparatus for determining the depth of the stack required for routing packets in an n-node network, and the interaction of such stack depth with label size. A further need exists for protocols for determining the stack depth and label size required for routing packets in an n-node network that strike a balance between smaller labels and smaller stacks.